package com.captain.leetcode.二维数组;

/**
 * @author captain
 * @Des 给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
 * <p>
 * 进阶：
 * <p>
 * 一个直观的解决方案是使用  O(mn) 的额外空间，但这并不是一个好的解决方案。
 * 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
 * 你能想出一个仅使用常量空间的解决方案吗？
 * @Date 2021/8/3 21:20
 */
public class 矩阵置零73 {

    public static void main(String[] args) {
        //[[0,1,2,0],[3,4,5,2],[1,3,1,5]]
        int[][] arr = new int[][]{{-1}, {2}, {3}};
        new 矩阵置零73().setZeroes(arr);
    }

    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        //1.遍历找出所有的0,记录下来
        boolean[][] arr = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    arr[i][j] = true;
                }
            }
        }
        //第二次循环
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (arr[i][j]) {
                    for (int k = 0; k < m; k++) {
                        matrix[k][j] = 0;
                    }
                    for (int l = 0; l < n; l++) {
                        matrix[i][l] = 0;
                    }
                }
            }
        }
    }
}


